package main

import (
	"fmt"

	. "local/algorithm/util"
)

var a []int = []int{}

func main() {
	t := generate([]int{})
	r := checkEqualTree(t)
	fmt.Println(r)
}

func generate(arr []int) *TreeNode {
	l1 := &TreeNode{Val: 2}
	l2 := &TreeNode{Val: 3}
	l3 := &TreeNode{Val: 4}
	l4 := &TreeNode{Val: 5}
	l5 := &TreeNode{Val: 6}
	l1.Right = l2
	l2.Right = l3
	l3.Right = l4
	l4.Right = l5
	return l1
}

//func generate(arr []int) *TreeNode {
//	root := &TreeNode{Val: 0}
//	left := &TreeNode{Val: -1}
//	right := &TreeNode{Val: 1}
//	root.Left = left
//	root.Right = right
//	return root
//}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
//var list []int
/**
给定一棵有 n 个结点的二叉树，你的任务是检查是否可以通过去掉树上的一条边将树分成两棵，且这两棵树结点之和相等
题意转化下:
以x为根的树所有结点值的和为sum(x)
如果sum(a)==sum(root)/2 ，那么可以以a节点开始切割，行程的两棵树的节点和相等，返回true，否则返回false
注意: (因为根节点的子树没有其他连接的边，也就不存在去掉一条边的说法，故a不能是根节点)
*/

func checkEqualTree(root *TreeNode) bool {
	if root == nil {
		return false
	}

	var list []int

	// 通过dfs计算整个树的权重，期间会遍历到每个节点，于是可以获得以各个节点为根的子树的权重，将子树权重保存在list中
	var sum func(root *TreeNode) int
	sum = func(root *TreeNode) int {
		if root == nil {
			return 0
		}
		tmp := sum(root.Left) + sum(root.Right) + root.Val // 左右中
		list = append(list, tmp)

		return tmp
	}

	total := sum(root)
	list = list[:len(list)-1] // root节点计算结果去除
	if total%2 == 0 {         // 这个判断不能省略，后面的total/2会自动floor，比如total为7 v为3 此时total/2为3 导致返回true
		for _, v := range list {
			if v == total/2 {
				return true
			}
		}
	}

	return false
}

func checkEqualTree(root *TreeNode) bool {
	if root == nil {
		return false
	}
	var sum func(root *TreeNode) int
	var list []int
	sum = func(root *TreeNode) int {
		if root == nil {
			return 0
		}

		tmp := root.Val + sum(root.Left) + sum(root.Right)
		list = append(list, tmp)
		return tmp
	}

	total := sum(root)
	list = list[:len(list)-2]
	if total%2 == 0 {
		for e := range list {
			if e == total/2 {
				return true
			}
		}

	}
	return false

}
